מיון מהיר (Quicksort) ואלגוריתם ה-Partition:

• הרעיון המרכזי (Divide & Conquer):
  • חלוקת המערך (Partition) ללא צורך בשלב המיזוג (Combine). המערך מחולק לשניים סביב איבר 'ציר' (Pivot).
  • צד אחד יכיל רק איברים קטנים או שווים לציר, והצד השני רק איברים גדולים ממנו.
• פעולת Partition:
  • בוחרת את האיבר הימני ביותר כציר. בזמן הסריקה היא מחזיקה 4 אזורים: ציר, אזור שטרם נבדק, אזור גדול מהציר ואזור קטן או שווה לציר.
  • זמן ריצה של Partition: ליניארי למספר האיברים - $\Theta (n)$.
• ניתוח זמן ריצה:
  • המקרה הגרוע:
    • אם המערך כל פעם מחולק ל-0 ו-m−1 איברים, נוסחת הנסיגה היא $T(n)=T(n-1)+n$
    • לכן, נקבל זמן ריצה של $\Theta (n^2)$
    • קורה כשהמערך ממוין מראש.
  • המקרה הטוב:
    • המערך מחולק בדיוק לחצי בכל צעד: $T(n)=2T(\frac{n}{2})+n$
    • לכן הסיבוכיות $\Theta (n\log n)$.
  • המקרה הממוצע / תוחלת (Randomized):
    • בהנחה שהקלט אקראי לחלוטין (או אם משתמשים בRandomized Quicksort שמגריל ציר במקום לקחת את הימני ביותר), התוחלת של זמן הריצה היא $\Theta (n\log n)$.

בעיית הבחירה (The Selection Problem):

• נתון מערך ואינדקס i, והמטרה היא למצוא את האיבר ה-i בגודלו.
• בחירה אקראית:
  • משתמש בפרוצדורת RandomizedPartition.
  • אם האינדקס המבוקש תואם בדיוק למיקום של הציר k לאחר החלוקה -מצאנו.
  • אחרת, מבצע קריאה רקורסיבית רק לאחד החצאים בהתאם למיקום i.
  • סה"כ תוחלת זמן הריצה היא חסם ליניארי של $\Theta (n)$.
• בחירה דטרמיניסטית ב-Select ו-ChoosePivot:
  • אלגוריתם זה מבטיח זמן ריצה של $\Theta (n)$ במקרה הגרוע באמצעות בחירה קפדנית של ציר טוב.
  • הפונקציה ChoosePivot מחלקת את המערך לקבוצות של 5 איברים. ממיינת כל קבוצה בנפרד למציאת החציון של כל 5 איברים. את כל החציונים היא מעתיקה למערך חדש B.
  • קריאה רקורסיבית מופעלת על המערך B כדי למצוא את "חציון החציונים", אשר ישמש בתור הציר שלנו ל-Partition.